/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-07-17
 * Time: 0:33
 */
//https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
//给定两个整数数组 preorder 和 inorder ，
// 其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
    public void print(){
        System.out.print(val+" ");
        if(left!=null){
            left.print();
        }
        if(right!=null){
            right.print();
        }
    }
}
public class Test {
    static int i=0;
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root=fun2(preorder,inorder,0,inorder.length-1);
        return root;
    }

    public static TreeNode fun2(int[] preorder, int[] inorder,int first,int last){
        if(last<first){
            return null;
        }
        int in=fun(preorder[i],inorder);
        TreeNode node=new TreeNode(preorder[i]);
        i++;
        node.left=fun2(preorder,inorder,first,in-1);
        node.right=fun2(preorder,inorder,in+1,last);
        return node;
    }

    public static int fun(int n,int[] arr){
        for(int i=0;i<arr.length;i++){
            if(arr[i]==n){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr={3,9,20,15,7};
        int[] brr={9,3,15,20,7};
        TreeNode root=buildTree(arr,brr);
        root.print();
    }
}
